package com.likeycy.my;

/**
 * @ClassName: MainTest
 * @Description: 简单测试案例反应算法对于实际问题的解决和时间上的取舍
 * @Author: sodagreen
 * @Date: 2021/2/20 2:11
 * @Version: 1.0
 */
public class MainTest {

    /**
     * 方法一：计算数字累加的和
     * @param n
     * @return
     */
    public static int sum1(int n) {
        int result = 0;
        for (int i = 1; i <= n; i++) {
            result += i;
        }
        return result;
    }

    /**
     * 方法二：公式计算数字累加的和
     * 所需时间复杂度：1 + 2 + 4 + 8 = 2^(n-1) -1 = 0.5 * 2^n -1 = O(2^n)
     * @param n
     * @return
     */
    public static int sum2(int n) {
        return (1 + n) * n / 2;
    }

    /**
     * 方法一：递归计算来实现斐波那契数列
     * 所需时间复杂度：O(n)
     * @param n
     * @return
     */
    public static int fib1(int n) {
        if (n <= 1) {
            return n;
        }
        return fib1(n -1) + fib1(n -2);
    }

    /**
     * 方法二：用递推算法来实现斐波那契数列
     * @param n
     * @return
     */
    public static int fib2(int n) {
        if (n <= 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        for (int i = 0; i < n - 1; i++) {
            int sum = first + second;
            first = second;
            second = sum;
        }
        return second;
    }

    /**
     * 方法三：改进方法二递推实现斐波那契数列
     * @param n
     * @return
     */
    public static int fib3(int n) {
        if (n <= 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        for (int i = 0; i < n-1; i++) {
            second = first + second;
            first = second - first;
        }
        return second;
    }

    /**
     * 方法四：改进方法三递推实现斐波那契数列
     * @param n
     * @return
     */
    public static int fib4(int n) {
        if (n <= 1) {
            return n;
        }
        int first = 0;
        int second = 1;
        while (n-- > 1) {
            second += first;
            first = second - first;
        }
        return second;
    }

    /**
     * 方法五：斐波那契数列线性代数解法
     * @param n
     * @return
     */
    public static int fib5(int n) {
        double c = Math.sqrt(5);
        double a = Math.pow((1 + c) / 2, n);
        double b = Math.pow((1 - c) / 2, n);
        //return (int)((Math.pow((1 + c) / 2, n) - Math.pow((1 - c) / 2, n)) / c);
        return (int) ((a - b) / c);
    }

    public static void main(String[] args) {
        int n = 29;

        TimeTool.check("sum1", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(sum1(n));
            }
        });

        TimeTool.check("sum2", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(sum2(n));
            }
        });


        TimeTool.check("Method：fib1", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(fib1(n));
            }
        });

        TimeTool.check("Method：fib2", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(fib2(n));
            }
        });

        TimeTool.check("Method：fib3", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(fib3(n));
            }
        });

        TimeTool.check("Method：fib4", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(fib4(n));
            }
        });

        TimeTool.check("Method：fib5", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(fib5(n));
            }
        });
    }
}
